package leetcode.tencent;

import leetcode.ListNode;
import leetcode.ListNodeUtil;

/**
 * @author Cheng Jun
 * Description: 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * https://leetcode-cn.com/problems/rotate-list/
 * @version 1.0
 * @date 2022/1/19 21:39
 */
public class rotateRight {

    public static void main(String[] args) {
        rotateRight(ListNodeUtil.getListNode(new int[]{1}), 1);
    }

    // 链表中节点的数目在范围 [0, 500] 内
    // -100 <= Node.val <= 100
    // 0 <= k <= 2 * 10^9

    // 解题思路：求 head 长度 length， k = k % length;
    // 截断 length - k 处，重新拼接

    // 输入：head = [1,2,3,4,5], k = 2
    // 输出：[4,5,1,2,3]
    static public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return head;
        int length = 0;
        ListNode pointer = head;
        // 获取 head 长度
        while (pointer != null) {
            pointer = pointer.next;
            length++;
        }
        // k 取余
        k = k % length;
        if (k == 0) return head;
        int counter = 1;
        pointer = head;
        ListNode newHead = pointer.next;
        // 找到链表中的切割点
        while (counter != length - k) {
            pointer = pointer.next;
            newHead = pointer.next;
            counter++;
        }
        pointer.next = null;
        pointer = newHead;
        // 找到新链表头 的尾节点，并把尾节点的 next 置为 head
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        pointer.next = head;
        return newHead;
    }
}
